// 图的邻接矩阵表示_无向网
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_VERTEX_NUM 20   // 最大顶点数
#define MaxInt 9999         // 边的最大权值，表示没有边的情况
// 状态码
typedef enum {OK, ERROR, OVERFLOW} Status;
 
// 图的种类
typedef enum {DG, DN, UDG, UDN} GraphKind;  // {有向图，有向网，无向图，无向网}
 
// 顶点类型
typedef int VertexType;
typedef int VRType;  // VRType是顶点关系类型，表示边的权值
typedef char InfoType;  // 边的附加信息类型
 
// 邻接矩阵的弧
typedef struct ArcCell {
    VRType adj;         // 边的权值
    InfoType *info;     // 边相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 
// 图的定义
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];  // 顶点向量
    AdjMatrix arcs;                   // 邻接矩阵
    int vexnum, arcnum;               // 图的顶点数和弧数
    GraphKind kind;                   // 图的种类
} MGraph;
 
// 查找顶点在顶点数组中的位置
int LocateVex(MGraph G, VertexType v) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vexs[i] == v) {
            return i;
        }
    }
    return -1;  // 如果未找到，返回-1
}
 
// 创建无向网
Status CreateUDN(MGraph *G) {
    int v1, v2, w, i, j;
 
    // 输入顶点数和边数
    printf("请输入顶点数和边数：");
    scanf("%d,%d", &(*G).vexnum, &(*G).arcnum);  // 输入总顶点数，总边数
 
    // 输入顶点信息
    printf("请输入各顶点的信息：\n");
    for (i = 0; i < (*G).vexnum; ++i) {
        printf("顶点 %d: ", i + 1);
        scanf("%d", &(*G).vexs[i]);  // 存入顶点表
    }
 
    // 初始化邻接矩阵，边的权值均置为极大值 MaxInt
    for (i = 0; i < (*G).vexnum; ++i) {
        for (j = 0; j < (*G).vexnum; ++j) {
            (*G).arcs[i][j].adj = MaxInt;
            (*G).arcs[i][j].info = NULL;  // 没有附加信息
        }
    }
 
    // 构造邻接矩阵
    printf("请输入边的信息 (v1, v2, 权值)：\n");
    for (int k = 0; k < (*G).arcnum; ++k) {
        printf("输入边 %d (v1 v2 w): ", k + 1);
        scanf("%d %d %d", &v1, &v2, &w);  // 输入一条边的信息：v1, v2, w
 
        i = LocateVex(*G, v1);  // 找到 v1 在顶点数组中的位置
        j = LocateVex(*G, v2);  // 找到 v2 在顶点数组中的位置
 
        if (i == -1 || j == -1) {
            printf("错误：顶点不存在！\n");
            return -1;
        }
 
        // 更新邻接矩阵中的权值
        (*G).arcs[i][j].adj = w;
        (*G).arcs[j][i].adj = w;  // 无向网，所以对称设置权值
    }
 
    return 0;  // 成功
}
 
// 打印图的邻接矩阵
void PrintGraph(MGraph G) {
    printf("图的邻接矩阵：\n");
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arcs[i][j].adj == MaxInt)
                printf("INF ");  // 表示没有边
            else
                printf("%d ", G.arcs[i][j].adj);  // 打印权值
        }
        printf("\n");
    }
}
 
int main() {
    MGraph G;
     
    // 创建无向网
    if (CreateUDN(&G) == 0) {
        PrintGraph(G);  // 打印图的邻接矩阵
    } else {
        printf("图创建失败！\n");
    }
 
    return 0;
}
